import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: wenxiwen
 * Date: 2022/3/25
 * Time: 14:51
 * Description: No Description
 */
public class TestDemo1 {
    public TestDemo1() {
    }

    public static void quick_sort(int[] nums, int l, int r){
        //b1. 迭代终止条件
        if(l>=r) {
            return;
        }

        //a1.初始化指针, 小技巧, 两端各走多一位. 利用do while 可少一特判.
        int i = l-1, j = r+1;
        int x = nums[l+r>>1];

        //a2.利用指针 如果左大右小. swap
        while(i<j){
            //a【2.1】 左指针大于中值 stop.
            do {
                i++;
            } while (nums[i] < x) ;
            //a【2.2】 右指针小于中值 stop.
            do {
                j--;
            } while(nums[j]>x);

            //a【2.3】 未达终止条件. swap
            if(i<j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        //b2. 迭代
        //传入参数还是边界.只有i,j指针在变动.
        //所以可以利用指针和传入参数分割出左右范围.
        quick_sort(nums,l,j);
        quick_sort(nums,j+1,r);
    }

    public static void main1(String[] args) {
        int[] arr = {2,4,5,1,3};
        quick_sort(arr,0,5-1);
        System.out.println(Arrays.toString(arr));

    }
}